//链表

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define TYPE int

typedef struct Node
{
	TYPE data;
	struct Node* next;
}Node;

//创建节点
Node* creat_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data=data;
	node->next = NULL;
	return node;
}

typedef struct List
{
	Node* head;
	Node* tail;
	size_t size;
}List;

//创建链表
List* creat_list(void);
//销毁链表
void destory_list(List* list);
//头添加
void head_add_list(List* list,TYPE data);
//尾添加
void tail_add_list(List* list,TYPE data);
//头删除
bool head_del_list(List* list);
//尾删除
bool tail_del_list(List* list);
//插入
bool insert_list(List* list,int index,TYPE data);
//位置删除
bool delete_index_list(List* list,int index);
//值删除
bool deleta_value_list(List* list,TYPE data);
//排序
void sort_list(List* list);
//遍历
void show_list(List* list);


int main()
{
	List* list = creat_list();
	for(int i = 0;i<10;i++)
	{
	//	tail_add_list(list,i);	
		head_add_list(list,i);	
	}
	sort_list(list);
	show_list(list);
	for(int i=0 ;i<1;i++)
	{
		tail_del_list(list);	
	}
	show_list(list);
}


//创建链表
List* creat_list(void)
{
	List* list = malloc(sizeof(List));
	list->head = NULL;
	list->tail = NULL;
	return list;	
}
//销毁链表
void destory_list(List* list)
{
	while(0<list->size)
	{
		head_del_list(list);
	}
	free(list);
}
//头添加
void head_add_list(List* list,TYPE data)
{
	Node* node = creat_node(data);
	if(0==list->size)
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		node->next=list->head;
		list->head=node;
	}
	list->size++;
}
//尾添加
void tail_add_list(List* list,TYPE data)
{
	Node* node =creat_node(data);
	if(0 == list->size )
	{
		list->head = node;
		list->tail = node;
	}
	else
	{
		list->tail->next = node;
		list->tail = node;
	}
	list->size++;
}


//头删除
bool head_del_list(List* list)
{
	if(0>=list->size)return false;

	Node* temp = list->head;
	list->head = temp->next;	
	if(1 == list->size)
	{`
		list->tail = NULL;
	}
	free(temp);
	list->size--;
	return true;
}
//尾删除
bool tail_del_list(List* list)
{
	if(0 >= list->size)return false;
	
	if(1==list->size)
	{
		head_del_list(list);
		return true;
	}
		
	Node* prev=list->head;
	while(prev->next!=list->tail)
	{
		prev = prev->next;	
	}
	free(list->tail);
	list->tail=prev;
	prev->next=NULL;
	list->size--;
	return true;

}

//插入
bool insert_list(List* list,int index,TYPE data)
{
	if(index < 0 || index >= list->size) return false;
	if(index == 0)
	{
		head_add_list(list,data);
		return true;
	}
	Node* prev=list->head;
	for(int i=0;i<index-1;i++)
	{
		prev = prev->next;	
	}

	Node* node = creat_node(data);
	node->next=prev->next;
	prev->next = node;
	list->size++;
	return true;
}


//位置删除
bool delete_index_list(List* list,int index)
{
	if(index<0 ||index>=list->size) return false;
	
	if(0 == index)
	{
		head_del_list(list);
		return true;
	}
	else if(list->size == index+1)
	{	
		tail_del_list(list);
		return true; 
	}
	else
	{
		Node* prev = list ->head;
		for(int i=0;i<index-1;i++)
		{
			prev=prev->next;	
		}
		Node* node = prev->next;
		prev->next=node->next;
		free(node);
		list->size--;
	}
	return true;
}
//值删除
bool deleta_value_list(List* list,TYPE data)
{	
	if(data == list->head->data)
	{
		head_del_list(list);
		return true;
	}
	Node* prev = list->head;
	while(NULL != prev->next)
	{
		if(data == prev->next->data)
		{
			Node* node = prev->next;
			prev->next = node->next;
			free(node);
			list->size--;
			return true;
		}
		prev = prev->next;
	}
	return false;
}

//排序
void sort_list(List* list)
{
	for(Node* node=list->head;node->next!=NULL;node=node->next)
	{
		for(Node* node1=node->next;NULL!=node1;node1=node1->next)
		{
			if(node->data > node1->data)
			{
				TYPE temp = node->data;
				node->data = node1->data;
				node1->data = temp;
			}
		}
	}
}
//遍历
void show_list(List* list)
{
	for(Node* node = list->head;NULL!=node;node=node->next)
	{
		printf("%d  ",node->data);	
	}
	printf("\n");
}


















